#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <string>

using namespace std;

typedef struct node *tree_ptr;		// node pointer
typedef struct node{
	tree_ptr llink;					// struct node has left-link part, right-link part, and key part
	int key;
	tree_ptr rlink;
};


typedef struct str *string_ptr;	// string pointer
typedef struct str {				// struct string has string name part and tree pointer part
	tree_ptr link;
} str;


// function declarations
tree_ptr insert_node(int X, tree_ptr T);
void	preorder(tree_ptr node),
		inorder(tree_ptr node),
		postorder(tree_ptr node);


bool flag_arrow; // flag for check print arrow or not

int main()
{
	
	int location;
	int key, cip;
	string str_input;
	char comma;
	tree_ptr root;
	char input[1024];

	printf("Type numbers to input : ");				// input numbers to input by string
	gets(input);
	root = NULL;
	location = 0;
	
	do{
		sscanf(&input[location], "%d", &key);		// put data one by one
	
		root = insert_node(key, root); // insert at BST

		for(cip = key ; cip!=0 ; cip = cip / 10){
			location++;									// find cipher
		}
		location++;
		sscanf(&input[location++], "%c", &comma);

	}while(input[location-1] != NULL);

	//printf("%s inserted!!\n\n", input);
	flag_arrow = false;
	printf("\nPreorder: ");
	preorder(root);
	flag_arrow = false;
	printf("\nInorder: ");
	inorder(root);
	flag_arrow = false;
	printf("\nPostorder: ");
	postorder(root);
	printf("\n");

	
	printf("Thank you for using this software!!\n");		// good bye
}

tree_ptr insert_node(int X, tree_ptr T)  
{  
	if( T == NULL )  
	{  
		/* Create and return a one-node tree */ 
		T = (tree_ptr)malloc( sizeof( struct node ) );  
		if( T == NULL )  
			printf( "Out of space!!!" );				// memory is full
		else 
		{  
			T->key = X;             
			T->llink = T->rlink = NULL; 
		}
	}  
	else {
		if( X < T->key )  
			T->llink = insert_node( X, T->llink );  
		else {
			if( X > T->key )  
				T->rlink = insert_node( X, T->rlink );
		}
		/* Else X is in the tree already; we'll do nothing */ 
	}
	return T;  // return tree_ptr T
}  

void inorder(tree_ptr node)		// in-order : LVR
{
	if(node) {
		inorder(node->llink);
		if(flag_arrow){
			printf("-> %d ", node->key);
		}else{
			printf("%d ", node->key);
			flag_arrow = true;
		}
		inorder(node->rlink);
	}
}

void preorder(tree_ptr node)	// pre-order : VLR
{
	if(node) {
		if(flag_arrow){
			printf("-> %d ", node->key);
		}else{
			printf("%d ", node->key);
			flag_arrow = true;
		}
		preorder(node->llink);
		preorder(node->rlink);
	}
}

void postorder(tree_ptr node)	// post-order : LRV
{
	if(node) {
		postorder(node->llink);
		postorder(node->rlink);
		if(flag_arrow){
			printf("-> %d ", node->key);
		}else{
			printf("%d ", node->key);
			flag_arrow = true;
		}
	}
}